package com.feiyue.learning.recursive;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

/**
 * 数字全排列：
 *      获取 123456 的全排列，比如 123456, 132456等
 * @author  feiyue
 * @date  2020/4/5
 */
public class NumberAllSort {
    private static int count = 0;

    public static void main(String[] args) {
        int[] numbers = new int[]{1, 2, 3, 4, 5, 6};
        printNumberAllSorts(numbers);
        System.out.println("总共全排列数：" + count);
    }

    private static void printNumberAllSorts(int[] numbers) {
        List<Integer> selected = new ArrayList<>(numbers.length);
        List<Integer> unSelected = IntStream.of(numbers).boxed().collect(Collectors.toList());

        recursiveNumber(selected, unSelected);
    }

    private static void recursiveNumber(List<Integer> selected, List<Integer> unSelected) {
        if (unSelected.size() == 0) {
            selected.stream().forEach(r->System.out.print(r + " "));
            System.out.println();
            count++;
            return;
        }

        for (int i = 0; i < unSelected.size(); i++) {
            Integer element = unSelected.get(i);

            List<Integer> tempSelected = new ArrayList<>(selected);
            List<Integer> tempUnSelected = new ArrayList<>(unSelected);

            tempSelected.add(element);
            tempUnSelected.remove(element);
            recursiveNumber(tempSelected, tempUnSelected);
        }
    }
}
